package realQuestion.yongyou;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Main2 {

    public int[] findCheap(int n, int[][] flights, int src) {
        int[][] prices = new int[n][n];
        for (int[] flight : flights
        ) {
            int u = flight[0];
            int v = flight[1];
            int w = flight[2];
            prices[u][v] = w;
        }


        PriorityQueue<int[]> pq = new PriorityQueue<>();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        pq.offer(new int[]{0, src});
        dist[src] = 0;

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int curPrice = cur[0];
            int curCity = cur[1];
            if (curPrice > dist[curCity]) {
                continue;
            }
            for (int i = 0; i < n; i++) {

                if (prices[curCity][i] > 0) {
                    int nextCity = i;
                    int nextPrice = curPrice + prices[curCity][i];

                    if (nextPrice < dist[nextCity]) {
                        dist[nextCity] = nextPrice;
                        pq.offer(new int[]{nextPrice, nextCity});
                    }

                }
            }

            for (int i = 0; i < n; i++) {
                if (dist[i] == Integer.MAX_VALUE) {
                    dist[i] = -1;
                }
            }

        }
        return dist;

    }
}
